package Java基础.值传递;

import java.util.PriorityQueue;

public class Main {
    static class  Person {
        private String name;
    }

    public int[] smallestK(int[] arr, int k) {
        //使用有限队列  可以自己实现一个最小堆
//        PriorityQueue<Integer> queue=new PriorityQueue<>();
        MinHeap minHeap=new MinHeap(arr.length);
        for (int i = 0; i < arr.length; i++) {
            minHeap.insert(arr[i]);
        }
        int res[]=new int[k];
        for (int i = 0; i < k; i++) {
            res[i]=minHeap.extractMin();
        }
        return res;
    }
    static class MinHeap {
        //用一个数组存储  capacity是容量 size是现在的大小
        private int[] heap;
        private int size;
        private int capacity;

        public MinHeap(int capacity) {
            this.capacity = capacity;
            this.size = 0;
            this.heap = new int[capacity];
        }

        // 获取父节点索引
        private int parent(int index) {
            return (index - 1) / 2;
        }

        // 获取左子节点索引
        private int leftChild(int index) {
            return 2 * index + 1;
        }

        // 获取右子节点索引
        private int rightChild(int index) {
            return 2 * index + 2;
        }

        // 交换堆中两个元素
        private void swap(int i, int j) {
            int temp = heap[i];
            heap[i] = heap[j];
            heap[j] = temp;
        }

        // 上浮操作
        private void siftUp(int index) {
            //parent(index) 如果父节点的值大于当前的
            while (index > 0 && heap[parent(index)] > heap[index]) {
                //进行交换值
                swap(parent(index), index);
                //index
                index = parent(index);
            }
        }

        // 下沉操作
        private void siftDown(int index) {
            int minIndex = index;
            int left = leftChild(index);
            int right = rightChild(index);
            if (left < size && heap[left] < heap[minIndex]) {
                minIndex = left;
            }
            if (right < size && heap[right] < heap[minIndex]) {
                minIndex = right;
            }
            if (index != minIndex) {
                swap(index, minIndex);
                siftDown(minIndex);
            }
        }

        // 插入元素
        public void insert(int value) {
            if (size == capacity) {
                throw new IllegalStateException("Heap is full");
            }
            heap[size] = value;
            siftUp(size);
            size++;
        }

        // 提取最小值
        public int extractMin() {
            if (size == 0) {
                throw new IllegalStateException("Heap is empty");
            }
            int min = heap[0];
            //将最后一个元素放到第一个  然后进行下浮操作
            heap[0] = heap[size - 1];
            size--;
            siftDown(0);
            return min;
        }

        // 获取最小值但不移除
        public int peekMin() {
            if (size == 0) {
                throw new IllegalStateException("Heap is empty");
            }
            return heap[0];
        }

        // 获取堆大小
        public int size() {
            return size;
        }
    }


}
